Binary gap

Time: O(1); Space: O(1); easy

Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.

If there aren’t two consecutive 1’s, return 0.

Example 1:

Input: N = 22

Output: 2

Explanation:

  • 22 in binary is 0b10110.

  • In the binary representation of 22, there are three ones, and two consecutive pairs of 1’s.

  • The first consecutive pair of 1’s have distance 2.

  • The second consecutive pair of 1’s have distance 1.

  • The answer is the largest of these two distances, which is 2.

Example 2:

Input: N = 5

Output: 2

Explanation:

  • 5 in binary is 0b101.

Example 3:

Input: N = 6

Output: 1

Explanation:

  • 6 in binary is 0b110.

Example 4:

Input: N = 8

Output: 0

Explanation:

  • 8 in binary is 0b1000.

  • There aren’t any consecutive pairs of 1’s in the binary representation of 8, so we return 0.

Constraints:

  • 1 <= N <= 10^9

[1]:

class Solution1(object):
    """
    Time: O(LogN)=O(1), due to n is a 32-bit number
    Space: O(1)
    """
    def binaryGap(self, N):
        """
        :type N: int
        :rtype: int
        """
        result = 0
        last = None

        for i in range(32):
            if (N >> i) & 1:
                if last is not None:
                    result = max(result, i-last)
                last = i

        return result

[2]:

s = Solution1()
N = 22
assert s.binaryGap(N) == 2
N = 5
assert s.binaryGap(N) == 2
N = 6
assert s.binaryGap(N) == 1
N = 8
assert s.binaryGap(N) == 0